/*
 * @lc app=leetcode.cn id=133 lang=typescript
 *
 * [133] 克隆图
 */

// @lc code=start
/**
 * Definition for Node.
 * class Node {
 *     val: number
 *     neighbors: Node[]
 *     constructor(val?: number, neighbors?: Node[]) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.neighbors = (neighbors===undefined ? [] : neighbors)
 *     }
 * }
 */

function cloneGraph(node: Node | null): Node | null {
  // 利用hash表记录节点的克隆
  const hash = new Map();
  // 利用递归遍历原图
  const clone = (node: Node | null): Node | null => {
    if (node === null) return null;
    if (hash.has(node)) return hash.get(node);
    const cloneNode = new Node(node.val, []);
    hash.set(node, cloneNode);
    // 遍历原图的所有邻居
    for (let neightbor of node.neighbors) {
      cloneNode.neighbors.push(clone(neightbor));
    }
    return cloneNode;
  };

  return clone(node);
}
// @lc code=end
